Problématique du bandit manchot

1. Notions d'exploitation et d'exploration

Pour comprendre les problématiques à venir que nous allons rencontrer dans la mise en place de l'apprentissage par renforcement, nous allons nous familiariser avec certains concepts relatifs au problème du bandit manchot.

Mais avant, revenons rapidement sur l'exemple "Frozen Lake" que nous avons traité précédemment. Imaginons qu'en se basant sur ses expériences, lorsque l'agent se retrouve à gauche d'un trou il choisit d'aller vers le haut. Cela lui garantit qu'il ne tombera pas dans un trou et ne perdra pas son gain. Cependant, l'agent n'a pas forcément exploré le choix d'éviter le trou en allant vers le bas. Il suit en fait une stratégie qu'il sait être bonne et qui lui permet de ne pas perdre ses gain. Il est dans l'exploitation de la stratégie. Si par contre l'agent décide de ne pas suivre sa stratégie et d'essayer une autre solution (aller vers le bas), alors l'agent est en mode exploration.

Cet exemple illustre le dilemme qu'il y a pour un agent entre l'exploitation et l'exploration, et qui doit être traité dans l'apprentissage automatique. La balance entre l'exploitation et l'exploration est un problème courant dans la vie de tous les jours. Par exemple, lorsque vous allez dans votre restaurant préféré, devez-vous prendre votre dîner favori ou bien essayer un nouveau menu ?

Il existe de nombreuses stratégies pour résoudre ce problème. Dans ce qui suit, nous allons étudier celle utilisable dans le cas du bandit manchot (Multi-Armed Bandits Problems - MABP), qui est utilisée dans de nombreux problèmes similaires qu'on trouve dans l'industrie.

2. Problème du bandit manchot

Le problème du bandit manchot peut être illustré de la manière suivante. Imaginez être dans un casino en train de jouer aux machines à sous, et que ces machines aient des probabilités de gain entre 35% et 65%. Comment peut-on dans ce cas trouver la machine avec la plus forte probabilité de gain, tout en minimisant le temps passé à faire des essais ? Au fur et à mesure des essais, l'agent construit et apprend la distribution des gains de chaque machine. L'objectif est ici de maximiser le gain obtenu, ce qui revient à trouver les options qui donnent les plus fortes récompenses et exploiter ces options le plus longtemps possible. Nous allons étudier deux approches pour résoudre ce problème : l'approche qui utilise la stratégie Epsilon-Greedy et celle qui utilise la notion de Upper Confidence Bound.

2.1 Approche Epsilon-Greedy

Avec cette méthode, l'agent apprend la meilleure stratégie permettant d'optimiser le gain en choisissant à chaque instant:

• Soit les actions optimales en se basant sur ce qu'il a appris lors de ses expériences précédentes (exploitation - approche de type greedy).
• Soit de nouvelles actions, différentes des actions optimales (exploration - approche de type epsilon).

La figure ci-dessous illustre ce concept.  
 

2.2 Upper Confidence Bound

L'algorithme Upper Confidence Bound (UCB) est basé sur le principe d'optimisme face aux évènement incertains. Il fait l'hypothèse que plus l'agent est incertain sur les probabilités d'une machine à sous, plus il est important d'explorer cette machine. Le programme définit trois machines à sous avec les trois probabilités normales suivantes:

• N1 ~ (0, 0.5²)
• N2 ~ (0.3, 1²)
• N3 ~ (0.6, 2²)

Les distributions précédentes montrent que la machine n°3 possède la plus grande variance et est donc la plus incertaine. L'algorithme UCB sélectionne donc la machine n°3 et reçoit une récompense dans le but de diminuer l'incertitude sur cette machine.

L'algorithme UCB est basé sur la formule suivante:

$${A_t} = \arg \mathop {\max }\limits_a \left\{ {{Q_t}\left( a \right) + c\sqrt {\frac{{\ln \left( t \right)}}{{{N_t}\left( a \right)}}} } \right\}$$

• ${A_t}$ : Action sélectionnée à l'instant $t$
• ${{N_t}\left( a \right)}$ : nombre de fois où l'action a été sélectionnée avant l'instant $t$.
• ${{Q_t}\left( a \right)}$ : Valeur de l'action à l'instant $t$
• $c>0$ : Coefficient permettant de contrôler le degré d'exploration

Le terme dans la racine carrée mesure l'incertitude sur l'action $a$ (le choix de la machine) à l'instant $t$ et le terme ${{Q_t}\left( a \right)}$ mesure la valeur de l'action $a$ l'instant $t$, c'est-à-dire une image du gain que cette action peut rapporter si on la choisie. Si ${{N_t}\left( a \right)}=0$ alors l'action $a$ est considérée comme une action optimale.

A chaque fois que l'agent choisit l'action $a$, l'incertitude diminue car ${{N_t}\left( a \right)}$ augmente et qu'il apparaît au dénominateur. A l'inverse, chaque fois qu'une action différente de $a$ est choisie, alors ${{N_t}\left( a \right)}$ n'augmente pas mais $ln(t)$ augmente. Comme ce terme intervient au numérateur, l'incertitude augmente.

L'utilisation du logarithme népérien permet de réduire la fréquence de sélection des action quand le temps augmente car la croissance de la fonction logarithme népérien diminue avec le temps.

Le bonus apporté par l'incertitude diminue donc car l'agent a davantage confiance dans l'action. Dans ce cas, ces actions seront moins souvent choisies.